/*
 * @lc app=leetcode.cn id=78 lang=typescript
 *
 * [78] 子集
 */

// @lc code=start
function subsets(nums: number[]): number[][] {
  // 子集枚举法，二进制
  const m = nums.length;
  // 位中1和nums索引的对应关系
  const mark: Map<number, number> = new Map();
  for (let i = 0, j = 1; i < 1 << m; i++, j <<= 1) {
    mark[j] = i;
  }

  const ans: number[][] = [];

  for (let i = 0; i < 1 << m; i++) {
    const res = [];
    // 枚举每一位1
    let val = i;
    while (val !== 0) {
      res.push(nums[mark[val & -val]]);
      val &= val - 1;
    }
    ans.push(res);
  }

  return ans;
}
// @lc code=end
